perm filename 2[NSF,BGB] blob
sn#058590 filedate 1973-08-18 generic text, type C, neo UTF8
COMMENT ā VALID 00006 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 2. WHAT WE PROPOSE TO DO.
C00009 00003 The micro language is composed of a small set of primitive
C00016 00004 Besides language inputs, a geometric modeling system should
C00022 00005 WHAT WE PROPOSE TO DO - An Itemized Shopping List.
C00025 00006
C00026 ENDMK
Cā;
2. WHAT WE PROPOSE TO DO.
We propose to represent and simulate solid objects in a
computer for the sake of mechanical design and mechanical drawing.
Our two year goal will be to automate as much as possible the task
of creating and altering three dimensional data structures from
which mechanical drawings can be derived. The overall project to
date has been called "geometric modeling" a term which we use to
refer to our particular combination of computer graphics, physical
world modeling, image processing and geometry. Accordingly, the
details of the work we propose doing will be presented in terms of
the elements comprising a Geometric Modeling System, GMS.
Like a computer, the four main elements of a geometric
modeling system are memory, process, input and output. Starting with
memory, there are the problems of representation (how to describe a
physical object); accessing (how to find a particular description by
name, by location, or by whether it is currently in view); and
efficiency (how to keep the size of storage space down and how to
dynamically allocate fast and slow memory resources).
The presently implemented explicit object representation is
based on polyhedron models of solid rigid objects. A simple object
called a body is defined by a surface shell composed of vertices,
edges and faces that satisfies the Euler equation, V - E + F = 2;
such polyhedron bodies are combined to form compound objects. At
present, curved objects are represented by approximating them using
a polyhedron composed of a sufficient number of flat polygonal
faces. We propose to further develope the appearance of curved
objects by automating the assignment of polygonal facets to a given
curved surface. Other current representation problems that we
propose working on include constructing efficient (and compatible)
object labeling, handling mechanical properties of an object, and
better representing compound and flexible objects.
A final representation issue we would study is that of a
format for communication of three dimensional models between
modeling systems. Although, we believe that it is too early to
propose a standard format; it is desirable to design and promulgate
a format as simple, but as inclusive as possible; and it is also
desirable to develope formatible I/O routines so that new formats
can be sent or received.
The usual input devices to a geometric modeling system
include keyboards, light-pens, joy-sticks, buttons, cameras and
film scanners; of which the most important to this proposal is the
keyboard because it is currently the best device for language input.
Indeed, we believe that we can demonstrate that a system based on
keyboards can do geometric control and editing better than a system
based on both a light pen and a keyboard. With respect to language,
we are proposing two projects: first, we would extend the programing
languages: FORTRAN, ALGOL and LISP; and second, we would continue
to develope our interactive edit and control language. The elements
of a language extension include new data types (the "memory" of our
system); a micro language of primitive operations and a macro
language of more complex operations.
The micro language is composed of a small set of primitive
functions that invoke the only subroutines allowed to directly
create and alter the data structure. All the geometric processors,
editors, input, output and higher language operations are
implemented in terms of these fewer than fifty primitives. The
reason for having a two level system is to isolate and minimize the
amount of code that is necessarily dependent on the implementation
details of the particular higher level language. Furthermore, it is
possible to construct primitives that are complete and general with
respect to fundamental principles in polyhedron topology and
geometry. For example, we now have a set of Euler primitives that
can generate any Eulerian polyhedron (and only Eulerian polyhedra);
as well as a set of Euclidean primitives for applying the group of
Euclidean transformations. With more good luck, we intend to
isolate sets of primitives for mechanics and for image formation.
The macro level of language extension is comprised of
operations that make it convenient to simulate building a mechanical
model of an object. The present macro level includes an operation
for "sweeping" edges into faces, and faces into solids; an
operation for "glueing" surfaces together; an operation for passing
"cutting" planes thru an object; and a most powerful trio of
operations for forming the volume union, intersection and
difference of two given polyhedra. Since polyhedra can be taken as
either bounding a finite solid volume or a finite empty volume; we
have found it convenient to draw some objects indirectly by building
their holes and intersecting the holes with their simple outer
shape. Further macro operations we propose to code would include
more "imaginery" ones for bending, constraining, filling,
enveloping, and expanding upon a skeleton; as well as some more
"realistic" operations that would model regular machine shop tools
such as a lathe, punch and milling machine; as well as machine
building processes such as welding, fastening and assembly.
Our second language project is oriented towards edit and
control. The main differences between an interactive graphics
editor and a graphics programming language is that an editor carries
along its working context so that most arguments and data do not
have to be explicitly named because they happen to be "at the top of
the stack" and are visibly intensified or otherwise indicated on the
display screen. The advantage of the interactive editor is that the
user is relieved of having to coin and call names of things, however
the disadvantage is that he can not develope subroutines of the
power available in a programming language which provides notation
for procedures, arguments, and variables. We plan to keep the
programming language level distinct from the control and edit
language level; although it should be clear that both language
levels are calling the same primitive execution routines.
Besides language inputs, a geometric modeling system should
have a way of reading data that is already in graphical form. For
such input, we propose using a television camera. For example, we
already have developed video intensity contouring to rapidly provide
the edges of an image in a form available for graphics editing.
Although video input per se is of secondary importance to this
proposal, we happen to have such hardware and software available at
Stanford and can make good use of it with little additional effort.
Furthermore, video (or visual) computer input has considerible
promise as a major input device of future computers.
The third element of a geometric modeling system are its
(software) processors. There are language processors, mechanical
simulators, locus solvers, image analysis and image synthesis, as
well as that process quite central to three dimensional drawing
which is hidden line (and surface) elimination. We have a hidden
line eliminator which combines several of the existing techniques
and which can generate both line drawings and video images; also we
have reason to believe that further work on our design will yield a
hidden eliminator that can handle apparently curved objects,
generate shadows, use the coherence between successive images, and
still be fast without special purpose hardware. Since the purpose
of the processors just mentioned should be sufficiently clear we
shall skip detailing their algorithms and implementation, although
this will comprise the bulk of the work and publication we propose
to do.
The fourth and final element of our modeling system is the
output, which includes dynamic CRT display, video display,
hardcopy printing, as well as magnetic tape. Although mundane, the
numerical object descriptions on conventional (non display) computer
media like magnetic tape is important in making the output of an
interactive display system available for further automatic
processing or communication. On the other hand, a high quality CRT
that can display characters and vectors is now and shall remain the
primary tool requiste to developing interactive graphics software;
consquently nearly a half of the budget included with this proposal
is allocated to aquiring such a CRT to enhance our existing display
system. The most promising alternative to a CRT is a video display;
however present day video display systems would require a very large
computer and fast memory to achieve the resolution and speed of a
CRT display.
WHAT WE PROPOSE TO DO - An Itemized Shopping List.
Ignoring the overall system organization and fine details,
the goals of the proposed project are summarized in the following
shopping list:
Items partially in hand.
1. Representation of solid rigid three dimensional polyhedra.
2. Language extension of geometric primitives.
3. Language extension of object building operations.
4. Polyhedron object hidden line (and surface) eliminator.
5. Geometric editor.
Items within one year's work.
6. Generation of mechanical drawings from geometric models.
7. Representation for the appearance of curved objects.
8. Representation for flexible objects.
9. Video acquisition of two dimensional drawings.
10. Mechanical simulation and animation.
Second year and/or elective Items.
11. Generation of high quality mechanical drawings.
12. Development of a remote display terminal version.
13. Development of a standard FORTRAN version.
14. Mechanical drawings for a special area of engineering;
(pipefitting, screw threading, mining, or whatever).
Basic research items.
15. Video acquisition of three dimensional objects.
16. Photometric simulation - shadows, multiple light sources;
for generation of high quality video appearance.
The most conservative estimate of our potential achievements
for the next two years would include the first five items listed,
since substantial work has already been done. Intermediate
expectations would include making considerable progress and original
contribution with respect to the items one through ten; as well as
doing one of the five items numbered eleven through fourteen.
Optimistic expectation would be to finish everything though item
sixteen.